//
// Created by 86152 on 2021/7/26.
//

#ifndef DATASTRUCTURE_GRAPH_H
#define DATASTRUCTURE_GRAPH_H

#include <iostream>
#include <string>
namespace graph{


    class Graph{

    public:
        std::string* name;
        int n;
        int** data;


        Graph(int n) : n(n) {
            name = new std::string [n];
            data = new int*[n];
            for (int i = 0; i < n; ++i) {
                data[i] = new int[n];
            }
        }

        virtual ~Graph() {
            for (int i = 0; i < n; ++i) {
                delete[] data[i];
            }
            delete[] data;
            delete[] name;
        }

        void input(int** array, char** name){

            for (int i = 0; i < n; ++i) {
                name[i] = name[i];

                for (int j = 0; j < n; ++j) {
                    data[i][j] = array[i][j];
                }
            }
        }

    };



    void Test(){
        Graph g(5);



    }


    void TopoSort(Graph& graph){
        int* inDrgee = new int[graph.n]{0};  // 计算所有点的入度
        int* outDrgee = new int[graph.n]{0};  // 计算所有点的入度
        int* stack = new int[graph.n]{0}; // 储存入度为0的点
        int* visited = new int[graph.n]{0}; // 记录访问
        int top = 0;


        for (int i = 0; i < graph.n; ++i) {
            for (int j = 0; j < graph.n; ++j) {
                if (graph.data[i][j] != 0){
                    inDrgee[j] += 1;
                    outDrgee[i] += 1;
                }
            }
        }

        for (int k = 0; k < graph.n; ++k) {
            if (inDrgee[k] == 0){
                stack[top++] = k;
            }
        }
        while (top != 0){
            int t = stack[--top];
            std::cout << t << " ";

            visited[t] = 1;
            for (int i = 0; i < graph.n; ++i) {
                if (visited[i] == 0 && graph.data[t][i] != 0){
                    inDrgee[i] -= 1;
                    if (inDrgee[i] == 0){
                        stack[top++] = i;
                    }
                }
            }
        }
        std::cout << std::endl;

        delete[] stack;
        delete[] visited;
        delete[] inDrgee;
        delete[] outDrgee;
    }


}


#endif //DATASTRUCTURE_GRAPH_H
